package LeetCode刷题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-26 15:34
 * @description: Functions of this class is
 * 官方解法：
 * 除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：
 *
 * 如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x - 1x−1 个元素为 xx。
 *
 * 在恢复后，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2
 *
 * 那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 xx 应当出现在数组中的 x - 1x−1 的位置，因此交换 nums[i] 和 nums[x−1]，这样 x 就出现在了正确的位置。在完成交换后，新的 [i]nums[i] 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 x∈[1,N]。
 *
 * 注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。
 *
 * 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 NN，整个方法的时间复杂度为 O(N)
 * for (int i = 0; i < nums.length; i++) {
 *             while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {//?????
 *                 swap(nums, i, nums[i] - 1);
 *             }
 *         }
 *         for (int i = 0; i < nums.length; i++) {
 *             if (nums[i] != i + 1) {
 *                 return i + 1;
 *             }
 *         }
 *         return nums.length + 1;
 *     }
 *
 *     private static void swap(int nums[], int i, int j) {
 *         int temp = nums[i];
 *         nums[i] = nums[j];
 *         nums[j] = temp;
 *     }
 **/
public class NoNoNo缺失的第一个正数 {
    public static void main(String args[]) {
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
    }

    public static int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
                //***关键就是在这里，因为第一次交换后，原先的位置上不一定是正确的顺序
                //所以要用一个while循环来进行多次交换
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    private static void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}